
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1737. -- [Usaco2005 jan]Naptime -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1737: [Usaco2005 jan]Naptime</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>58&nbsp;&nbsp;<span class=green>Solved: </span>39<br>[<a href='submitpage.php?id=1737'>Submit</a>][<a href='problemstatus.php?id=1737'>Status</a>][<a href='bbs.php?id=1737'>Discuss</a>]</center><h2>Description</h2><div class=content>Goneril is a very sleep-deprived cow. Her day is partitioned into
N (3 <= N <= 3,830) equal time periods but she can spend only B (2
<= B < N) not necessarily contiguous periods in bed.  Due to her
bovine hormone levels, each period has its own utility U_i (0 <=
U_i <= 200,000), which is the amount of rest derived from sleeping
during that period.  These utility values are fixed and are independent
of what Goneril chooses to do, including when she decides to be in
bed.

With the help of her alarm clock, she can choose exactly which
periods to spend in bed and which periods to spend doing more
critical items such as writing papers or watching baseball. However,
she can only get in or out of bed on the boundaries of a period.

She wants to choose her sleeping periods to maximize the sum of the
utilities over the periods during which she is in bed.  Unfortunately,
every time she climbs in bed, she has to spend the first period
falling asleep and gets no sleep utility from that period.

The periods wrap around in a circle; if Goneril spends both periods
N and 1 in bed, then she does get sleep utility out of period 1.

What is the maximum total sleep utility Goneril can achieve?

一只牛想在N段相等的时间内选择B段睡觉。每一段时间的睡眠都会给这只牛不同程度的体力恢复。总的体力恢复值就是所有睡眠时间段的恢复值之和，但是每一次连续睡眠的第一段时间不会给牛带来任何体力恢复（它还没有睡着），而且所有N段时间形成一个环，即可以认为第(N+1)段时间就是第1段时间。 
给定N，B以及每段时间的体力恢复值ai，要求最大的总体力恢复值。 </div><h2>Input</h2><div class=content>* Line 1: Two space-separated integers: N and B

* Lines 2..N+1: Line i+1 contains a single integer, U_i, between 0 and
        200,000 inclusive

</div><h2>Output</h2><div class=content>* Line 1: A single integer, the maximum total sleep utility Goneril
        can achieve.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>5 3<br />
2<br />
0<br />
3<br />
1<br />
4<br />
<br />
INPUT DETAILS:<br />
<br />
The day is divided into 5 periods, with utilities 2, 0, 3, 1, 4 in that <br />
order. Goneril must pick 3 periods.<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>6<br />
<br />
OUTPUT DETAILS:<br />
<br />
Goneril can get total utility 6 by being in bed during periods 4,<br />
5, and 1, with utilities 0 [getting to sleep], 4, and 2<br />
respectively.</span></div><h2>HINT</h2>
			<div class=content><p>见国家队2005 Twb,ZgL作业</p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1737'>Submit</a>][<a href='problemstatus.php?id=1737'>Status</a>][<a href='bbs.php?id=1737'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
